package com.liunian.algorithmstudy.backtracking.partition;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses93 {

	/**
	 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
	 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
	 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。
	 你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

	 示例 1：
	 输入：s = "25525511135"
	 输出：["255.255.11.135","255.255.111.35"]

	 示例 2：
	 输入：s = "0000"
	 输出：["0.0.0.0"]

	 示例 3：
	 输入：s = "101023"
	 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
	 */
	List<String> res = new ArrayList<>();
	StringBuilder path = new StringBuilder();
	public List<String> restoreIpAddresses(String s) {
		backTracking(s, 0, 0);
		return res;
	}

	private void backTracking(String s, int index, int dot) {
		if (dot == 4) {
			if (index == s.length()) {
				res.add(path.substring(0, path.length() - 1));
			}
			return;
		}

		for (int i = index; i < s.length(); i++) {
			if (isValid(s, index, i + 1)) {
				dot++;
				path.append(s.substring(index, i + 1)).append(".");
				backTracking(s, i + 1, dot);
				path.delete(index + dot - 1, path.length());
				dot--;
			} else {
				break;
			}
		}

	}

	private boolean isValid(String s, int left, int right) {
		String substring = s.substring(left, right);
		if (right - left > 3) {
			return false;
		}
		for (int i = 0; i < substring.length(); i++) {
			if (substring.charAt(i) < '0' || substring.charAt(i) > '9') {
				return false;
			}
		}
		if (substring.length() > 1 && substring.charAt(0) == '0') {
			return false;
		}
		if (Long.parseLong(substring) > 255) {
			return false;
		}
		return true;
	}

	public static void main(String[] args) {
		RestoreIpAddresses93 r = new RestoreIpAddresses93();
		System.out.println(r.restoreIpAddresses("99999999999999999999"));
	}

}
